This invention relates generally to computer graphics and to the rendering of three dimensional images. More particularly, it relates to compression and decompression of surface normal data used in the rendering of three dimensional images.
For three dimensional images generated from abstract platonic primitives, such as lines and polygons, computer graphics applications and systems store primitive vertex information such as coordinates of surface points, associated surface normals, and other rendering information such as opacity, color, etc. Surface normals are vectors and as such are defined by a length and a direction. They can be represented in Cartesian coordinates by the coordinates {x,y,z} of a parallel vector of the same length whose starting point is the coordinate system origin.
This procedure for storing surface normals as a set of three floating point numbers introduces several problems. First, floating-point number representations of Cartesian coordinates often provide more precision than needed for realistic visual representation resulting in inefficient use of the resources of memory and computation time. Second, storing a surface normal as an {x,y,z} Cartesian vector does not guarantee that the surface normal is of unit length, i.e. the distance from the origin to the point {x,y,z} is one. Graphics libraries in common use expect to receive surface normal data in unit length and must scale the length of the surface normals to one, if they are not received as such. And third, using common single precision floating point formats, the total space required to store a surface normal is three 32-bit full words, or 12 bytes. When several hundred thousand surface normals need to be stored, along with other geometric and application data, upper bounds on system memory resources can be reached. This inefficient use of memory limits the maximum size and resolution of the image that can be rendered at any given time.
A common technique used to address the above problems is to represent and store surface normals as spherical coordinates instead of Cartesian coordinates. Using this technique two floating point values are specified, one for the longitude or polar angle and one for the latitude or azimuthal angle, which results in a 3:2 data compression ratio for the unit length surface normal. Required memory could be reduced further, with reduced precision, by storing the latitude and longitude as two short integers, each of which requires 2 bytes of memory in common systems, for a total of 4 bytes, resulting in a 3:1 data compression ratio. However, the numeric precision is not uniform between the two coordinate values of longitude and latitude. If the normal position is near latitude xcfx80/2 or xe2x88x92xcfx80/2 (i.e., near the poles), the longitude value provides much greater precision than when the latitude is near 0 (i.e., near the equator). Also, conversion from spherical coordinates to Cartesian coordinates for graphics processing is computationally expensive.
Another technique for storing the unit length surface normals is to use an abstract single number representation. This technique involves a tessellation of a sphere obtained by combining the vertices of two platonic solids, the icosahedron and the dodecahedron. Then, a 4-deep triangle subdivision of the resulting 60 equilateral triangles is performed giving a sphere covered with 7680 triangles. A surface normal is mapped into an abstract value by first determining which of the original 60 triangles contains the normal. Then 128 dot products with the normal to the 128 interior triangles are performed. The largest dot product indicates the best matching triangle for the incoming normal. The result of these computations is used as the compressed normal. To decompress, the compressed normal is used to index a table of pre-computed values. Calculation of the numerous dot products required in this technique is computationally inefficient. Higher resolution, i.e., more and smaller triangles, results in even more involved computations. Much of the memory savings inherent in this technique is lost because of the size of the lookup table. Also, the range of compressed normals is limited by the size of the decompression table which puts an upper limit on their precision. This technique is often used to map normals to pre-computed lighting values using a lookup table as above with the lighting values instead of normals. Used in this manner, when the lighting direction to the model is changed, the values in the look-up table must be recomputed, resulting in additional computation time. Because a lighting look-up table is used, this algorithm does not address the issue of scaling the original surface normal coordinates for unit length, and thus is not a data compression technique in the purest sense.
Still another method uses an abstract single number as an index into a table of surface normals based on the tessellation of a unit sphere. Because of the symmetry of the unit sphere, the table size can be reduced by dividing the unit sphere into identical octants bounded by the x=0, y=0, and z=0 planes. This division results in a triangular shaped area which is further folded into identical sextants bounded by the x=y, y=z, and x=z planes. The resulting table size is reduced by a factor of 48.
In a further refinement of the previous method, the normal is encoded as two orthogonal angular addresses. This coding technique allows selection of the resolution of the surface normal by increasing or reducing the number of bits in each angular address. Further reduction of normal size is possible by encoding the normal index using a variable length delta-encoding where only the difference between adjacent normals is encoded. This technique can reduce the size of an encoded normal by half.
Such methods result in high compression, but are computationally expensive to compress and decompress. In addition, employing an index into a table consumes a large amount of memory in storing the table and incurs a performance penalty in accessing values from the table. Also, encoding the surface normal as two orthogonal angular addresses introduces data alignment issues which slow memory access and require special code to access and align the data for processing.
Therefore, in order to better meet the dual requirements of reduced memory utilization which permits more geometry to be loaded into memory and of higher speed which increases rendering performance, a need exists for further improvements in compression methods used in storing surface normal data for use in rendering three dimensional images.
In a representative embodiment of the methods for compression of a surface normal, if not already of unit length, the surface normal is first scaled to unit length in Cartesian coordinates. The vector component of the surface normal having the largest magnitude is identified. Then the two remaining vector components are stored in a predefined order and in a memory space whose combined size is a preselected number of bytes less at least three bits, two bits of which is the number of bits necessary to store an indicator of the vector component not stored and one bit of which indicates the algebraic sign of that vector component. For example, if z is the largest component of the surface normal, {x,y} are stored in that order; if y is the largest component, {x,z} are stored in that order; and if x is the largest component, {y,z} are stored in that order. In a representative embodiment, if the preselected number of bytes is four (32 bits), each of the two stored vector components including the algebraic sign and exponent of that component is stored in 14 bits. At least two of the remaining bits are used to indicate which of the three vector components {x,y,z} is not stored, and an additional bit is used to store the sign of the vector component not stored. Alternatively three bits could be used to indicate which of the three vector components {x,y,z} is not stored, since that bit would otherwise not be used.
Decompression of the surface normal requires first scaling the two stored vector components into floating-point values for the operating system in use. Since the two vector components stored were vector components of a unit length surface normal, the third vector component is obtained from the definition of a three-dimensional unit length, i.e., from the following equation: 1=X2+y2+z2. As an example if x and y were the vector components that were stored, z is the non-stored vector component and is obtained from
z=+/xe2x88x92{square root over (1xe2x88x92x2xe2x88x92y2+L )}
with the sign of z being determined from the sign bit which was stored as indicated above.
Compressed surface normals obtained using methods of a representative embodiment of the present invention would enable graphics applications to display larger geometry data sets with higher performance than would otherwise be possible without compression. The methods used in the representative embodiments are simple and fast. They can be implemented in graphics hardware with minimal cost and complexity and with full graphics performance. Also, decompressed surface normals are by definition of unit length. Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. The details disclosed in the specification should not be read so as to limit the invention.